//
//  main.cpp
//


//  
//  Copyright (c) Vikas K. Garg [http://ttic.uchicago.edu/~vkg/]. All rights reserved.  This is a free software 
//  distributed without any warranty: you are free to use/modify/redistribute this code for your purpose or 
//  redistribute it under the terms of the GNU General Public License as published by the Free Software Foundation.


// --------------------------------------------------------------------------------------------------------------

/* This is a sample main file to integrate the modules of the mini library that illustrates various operations related 
   to the Binary Search Tree (BST) abstract data type (ADT). */

// Acknowledgments: Being a fan of recursion, I have resorted to using recursion in one way or the other. Of course, 
// exactly the same effect can be accomplished without recursion. Ever since I got introduced to data structures, I 
// have been a big fan of trees, which to me are the coolest data structures (along with graphs) and really fun to code
// and play with! :) Much of the work here is inspired by the wonderful enunciation of the text in several standard 
// books on data structures including those by Lipschutz (Schaum Series), Knuth (The Art of Computer Programming), 
// Cormen et. al (popularly known as CLRS), Sedgewick (probably the best book on recursion out there!), 
// Horowitz-Sahni, Kruse-Leung-Tondo, Tenenbaum, Brassard-Bratley, Aho-Ullman-Hopcroft, and Weiss (a beautiful book!).
// Much of my coding style here derives from the book by Mark Weiss. I am grateful to Prof. Yury Makarychev at TTI-C
// [http://ttic.uchicago.edu/~yury/] for his extremely insightful comments and constructive feedback.


// ---------------------------------------------------------------------------------------------------------------

#define InvalidMenu -7
#include "BinarySearchTreeADTHeader.h"
#include <iostream>
using namespace std;


int exception_flag=0;

int main()
{
    node *root=NULL;
    int opt,num;
    char ch;
    int flag=0;
    string s;
    do
    {
        opt=menu();
        if (opt==InvalidMenu)        
            break;
        flag=0;
        switch(opt)
        {
            case 1:      //Create a tree from a vector of numbers
                delete_tree(root);    //delete the previous tree if it existed
                root=NULL;
                cout<<endl<<"Enter the no. of elements in the vector"<<endl;
                int n;
                try
                {
                    cin>>s;
                    stringstream ss;
                    ss<<s;
                    if(ss>>n && n>=0)   //Check for valid input
                    {
                        getline(cin,s);
                        stringstream ss_discard;
                        ss_discard<<s;
                        cout<<endl<<"Enter "<< n<< " element(s)"<<endl;
                    }
                    else 
                        throw handleInvalidInputCreateTree();
                }
                catch(handleInvalidInputCreateTree &e)
                {
                    //cout<<e.what()<<endl;  //Uncomment this line if you want to print the error message
                    stringstream ss_discard;
                    getline(cin,s);
                    ss_discard<<s;
                    cout<<"Error code: "<< e.code()<<endl;
                    exception_flag=1;
                    break;
                }
                try
                {
                    for(int i=0;i<n;i++)
                    {
                        cin>>s;
                        stringstream ss;
                        ss<<s;
                        if(ss>>num && num>0)
                           root=insert(root,num);
                        else 
                            throw handleInvalidInsert();
                    }
                    //Discard extraneous input if any
                    stringstream ss_discard;
                    if(getline(cin,s))
                       ss_discard<<s;
                }
                catch(handleInvalidInsert &e)
                {
                    stringstream ss_discard;
                    getline(cin,s);
                    ss_discard<<s;
                    //cout<<e.what()<<endl;  //Uncomment this line if you want to print the error message
                    cout<<"Error code: "<< e.code()<<endl;
                    exception_flag=1;
                    break;
                }
                break;
            case 2:     //Insert an element in the tree
                do
                {
                    cout<<endl<<"Enter the element to be inserted"<<endl;
                    cin>>s;
                    try
                    {
                        stringstream ss;
                        ss<<s;
                        if(ss>>num && num>0)
                        {
                            root=insert(root,num);
                            stringstream ss_discard;
                            getline(cin,s);
                            ss_discard<<s;
                            cout<<"Insert another element(y/n)?"<<endl;
                            cin>>ch;
                            try
                            {
                                if(ch!='y' && ch!='n')
                                    throw handleInvalidPerformOption();
                                else 
                                {
                                    stringstream ss_discard;
                                    getline(cin,s);
                                    ss_discard<<s;
                                }
                            }
                            catch(handleInvalidPerformOption &e)
                            {
                                //cout<<e.what()<<endl;  //Uncomment this line if you want to print the error message
                                stringstream ss_discard;
                                getline(cin,s);
                                ss_discard<<s;
                                cout<<"Error code: "<< e.code()<<endl;
                                break;
                            }
                        }
                    else
                        throw handleInvalidInsert();
                    }
                    catch(handleInvalidInsert &e)
                    {
                        stringstream ss_discard;
                        getline(cin,s);
                        ss_discard<<s;
                        //cout<<e.what()<<endl;  //Uncomment this line if you want to print the error message
                        cout<<"Error code: "<< e.code()<<endl;
                        exception_flag=1;
                        break;
                    }
                }while(ch=='y');
                break;
            case 3:    //Delete an element from the tree
                do
                {
                    if(root==NULL)
                        cout<<endl<<"Empty tree: Deletion not possible"<<endl;
                    else
                    {
                        cout<<endl<<"Enter the element to be deleted"<<endl;
                        cin>>s;
                        try
                        {
                            stringstream ss;
                            ss<<s;
                            if(ss>>num && num>0)
                            {
                                root=del(root,num);
                                stringstream ss_discard;
                                getline(cin,s);
                                ss_discard<<s;
                                cout<<endl<<"Delete another element(y/n)?"<<endl;
                                cin>>ch;
                                try
                                {
                                    if(ch!='y' && ch!='n')
                                        throw handleInvalidPerformOption();
                                    else 
                                    {
                                        stringstream ss_discard;
                                        getline(cin,s);
                                        ss_discard<<s;
                                    }
                                }
                                catch(handleInvalidPerformOption &e)
                                {
                                    //cout<<e.what()<<endl;  //Uncomment this line if you want to print the error message
                                    stringstream ss_discard;
                                    getline(cin,s);
                                    ss_discard<<s;
                                    cout<<"Error code: "<< e.code()<<endl;
                                    break;
                                }
                            }
                            else 
                                throw handleInvalidDelete();
                        }
                        catch(handleInvalidDelete &e)
                        {
                            //cout<<e.what()<<endl;  //Uncomment this line if you want to print the error message
                            stringstream ss_discard;
                            getline(cin,s);
                            ss_discard<<s;
                            cout<<"Error code: "<< e.code()<<endl;
                            exception_flag=1;
                            break;
                        }
                    }
                }while(ch=='y');
                break;
            case 4:     //Preorder traversal
                if(root==NULL)
                    cout<<endl<<"Empty tree";
                else
                    preorder(root);
                break;
            case 5:    //Inorder traversal
                if(root==NULL)
                    cout<<endl<<"Empty tree";
                else
                    inorder(root);
                break;
            case 6:   //Postorder traversal
                if(root==NULL)
                    cout<<endl<<"Empty tree";
                else
                    postorder(root);
                break;
            case 7:   //Level-by-level traversal
                if(root==NULL)
                    cout<<endl<<"Empty tree";
                else
                {
                    lnode *front,*rear;
                    front=rear=NULL;
                    front=new lnode;
                    front->a=root;
                    front->next=NULL;
                    rear=front;
                    levelorder(root,front,rear);
                }
                break;
            case 8:  //Form a sorted circular double linked list
                if(root==NULL)
                    cout<<endl<<"Empty tree:Empty double circular linked list";
                else
                {
                    dnode *temp,*head;
                    head=new dnode;
                    head->next=head->prev=head;
                    TreeToList(&head,root);
                    cout<<endl<<"First to Last traversal"<<endl;
                    for(temp=head->next; temp!=head; temp=temp->next)
                        cout<<temp->info<<'\t';
                    cout<<endl<<endl<<"Last to First traversal"<<endl;
                    for(temp=head->prev;temp!=head;temp=temp->prev)
                        cout<<temp->info<<'\t';
                    //Free the memory by deleting the circular list
                    for(temp=head->next; temp!=head; )
                    {
                        dnode *next_dnode=temp->next;
                        head->next=next_dnode;
                        next_dnode->prev=head;
                        temp->next=NULL;
                        temp->prev=NULL;
                        delete temp;
                        temp=head->next;
                    }
                    head->next=NULL;
                    head->prev=NULL;
                    delete head;
                }
                break;
            case 9:   //Mirror image
                if(root==NULL)
                    cout<<endl<<"Empty tree";
                else
                    root=mirror(root);
                break;
            case 10: //Sum of leaves
                if(root==NULL)
                    cout<<endl<<"Empty tree:Sum undefined";
                else
                {
                    int sum=0;
                    sum_leaves(root,&sum);
                    cout<<endl<<"Sum of leaves="<<sum;
                }
                break;
            case 11:  //Height of the tree
                if(root==NULL)
                    cout<<endl<<"Empty tree:Height not defined";
                else
                {
                    int height;
                    height=lmax(root,-1);
                    cout<<endl<<"Maximum level(height) of tree="<<height;
                }
                break;
            case 12: //Minimum depth of a leaf
                if(root==NULL)
                    cout<<endl<<"Empty tree:Height not defined";
                else
                {
                    int height;
                    height=lmin(root);
                    cout<<endl<<"Minimum level="<<height;
                }
                break;
            case 13: //Type of the tree
            {
                int type=1;
                if(root==NULL)
                    cout<<endl<<"Empty tree";
                else
                {
                    findtype1(root,&type);
                    if(type==1)
                        cout<<endl<<"Strictly binary";
                    else
                        cout<<endl<<"Not Strictly binary";
                    int min_height,max_height;
                    min_height=lmin(root);
                    max_height=lmax(root,-1);
                    if(min_height==max_height && type==1)
                        cout<<endl<<"Complete tree";
                }
                break;
            }
            case 14:  //Path with a given sum
            {
                int sumpath;
                int sum = 0; 
                cout<<endl<<"Enter the sum of the path: ";
                cin>>s;
                int found = 0;
                try
                {
                    stringstream ss;
                    ss<<s;
                    if(ss>>sumpath && sumpath > 0)
                    {
                        stringstream ss_discard;
                        getline(cin,s);
                        ss_discard<<s;
                        pathsum(root,sumpath,&found, &sum);
                        if(found==0)
                            cout<<endl<<"No path with sum "<<sumpath<<" found";
                    }
                    else 
                       throw handleInvalidPathSum();
                }
                catch(handleInvalidPathSum &e)
                {
                    //cout<<e.what()<<endl;  //Uncomment this line if you want to print the error message
                    stringstream ss_discard;
                    getline(cin,s);
                    ss_discard<<s;
                    cout<<"Error code: "<< e.code()<<endl;
                    exception_flag=1;
                    break;
                }
                break;
            }
            case 15:  //Nth smallest element
            {
                int kSmallest;
                int found = 0, j=0;
                cout<<endl<<"Enter the value of N: ";
                cin>>s;
                try
                {
                    stringstream ss;
                    ss<<s;
                    if(ss>>kSmallest && kSmallest > 0)
                    {
                        stringstream ss_discard;
                        getline(cin,s);
                        ss_discard<<s;
                        NSmallest(root, kSmallest, &found, &j);
                        if(found==0)
                            cout<<endl<<"Element not found";
                    }
                    else 
                        throw handleInvalidNSmallest();
                }
                catch(handleInvalidNSmallest &e)
                {
                    //cout<<e.what()<<endl;  //Uncomment this line if you want to print the error message
                    stringstream ss_discard;
                    getline(cin,s);
                    ss_discard<<s;
                    cout<<"Error code: "<< e.code()<<endl;
                    exception_flag=1;
                    break;
                }
                break;
            } 
            case 16: //Clone the tree
            {
                node *clone_tree = NULL;
                clone_tree = clone(root);
                if(clone_tree)
                {
                    cout<<endl<<"The tree has been cloned successfully\n";
                    cout<<endl<<"In-order traversal of the cloned tree\n";
                    inorder(clone_tree);
                    cout<<endl<<"Pre-order traversal of the cloned tree\n";
                    preorder(clone_tree);
                    cout<<endl<<"Post-order traversal of the cloned tree\n";
                    postorder(clone_tree);
                    cout<<endl;
                    delete_tree(clone_tree);   //free the memory occupied by the clone tree. 
                }
                else 
                   cout<<endl<<"Clone tree is empty\n";
                break;
            }
            case 17: //Delete the tree and free the memory
            {
                delete_tree(root);
                root = NULL;
                break;
            }
            case 18: //Obtain a vector from the tree
            {
                vector<int>TreeVector(0);   //Create an empty vector
                TreeToVector(root, &TreeVector);
                cout<<endl;
                for(int i=0; i<TreeVector.size(); i++)
                    cout<<TreeVector[i]<<" ";
                break;
            }
            case 19: //Obtain an STL list from the tree
            {
                list<int>TreeList(0);
                TreeToListSTL(root, &TreeList);
                cout<<endl;
                for (list<int>::iterator it = TreeList.begin(); it != TreeList.end(); it++)
                    std::cout << *it << ' ';
                break;
            }
            case 20: //Determine the number of nodes in the tree
            {
                int size = 0;
                size = TreeSize(root, &size);
                cout<<endl<<size<<endl;
                break;
            }
                
            default:
                cout<<endl<<"Invalid option: Expected an integer between 1 and 20 (including both)"<<endl;
        }
        if (exception_flag==1)
        {
            ch='y';
            exception_flag=0;
        }
        else
        {
            cout<<endl<<"Perform another operation(y/n)?"<<endl;
            cin>>ch;
            try
            {
                if(ch!='y' && ch!='n')
                   throw handleInvalidPerformOption();
                else 
                {
                    stringstream ss_discard;
                    getline(cin,s);
                    ss_discard<<s;
                }
            }
            catch(handleInvalidPerformOption &e)
            {
                //cout<<e.what()<<endl;  //Uncomment this line if you want to print the error message
                stringstream ss_discard;
                getline(cin,s);
                ss_discard<<s;
                cout<<"Error code: "<< e.code()<<endl;
                break;
            }
        }
    }while(ch=='y');
delete_tree(root);     //Delete the tree and free the memory if not done already
return 0;
}


